class Solution {
public:

    int totalNQueens(int n) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if (n <= 0) {
            return 0;
        }
        vector<bool> flags0(2 * n - 1, false);
        vector<bool> flags1(2 * n - 1, false);
        vector<int> q(n);
        int ans = 0;

        for (int i = 0; i < n; ++i) {
            q[i] = i;
        }

        dfs(0, flags0, flags1, q, ans);
        return ans;

    }

    void dfs(int depth, vector<bool> &flags0, vector<bool> &flags1, vector<int> &q, int &ans) {
        if (depth == q.size()) {
            ++ans;
            return;
        }
        int n = q.size();
        for (int i = depth; i < n; ++i) {
            int x = depth;
            int y = q[i];
            if (flags0[x + y] || flags1[x - y + n - 1]) {
                continue;
            }
            flags0[x + y] = true;
            flags1[x - y + n - 1] = true;
            swap(q[depth], q[i]);
            dfs(depth + 1, flags0, flags1, q, ans);
            swap(q[depth], q[i]);
            flags1[x - y + n - 1] = false;
            flags0[x + y] = false;
        }
    }
};
